
\section{最大公约数和最小公倍数问题(p1029)}
\subsection{题目描述}
输入2个正整数$x0,y0(2 \leq x0 < 100000, 2 < y0 \leq 1000000)$,求出满足下列条件的P,Q的个数 \\
条件:
\begin{compactitem}
\item P,Q是正整数
\item 要求P,Q以x0​为最大公约数,以y0​为最小公倍数. 
\end{compactitem}
试求:满足条件的所有可能的2个正整数的个数.

\subsection {输入格式}
 $2$个正整数$x_0,y_0$

\subsection {输出格式}
$1$个数，表示求出满足条件的$P,Q$的个数

\subsection {样例}
\textbf{输入}
\begin{lstlisting}
3 60
\end{lstlisting}

\textbf{输出}
\begin{lstlisting}
4
\end{lstlisting}

\subsection {说明}
$P,Q$有4种
\begin{compactitem}
\item 3,60
\item 15,12
\item 12,15
\item 60,3 
\end{compactitem}

\subsection{分析}
本题的解题思路是：
\begin{compactitem}
\item 先把从x0到y0之间所有能被x0整除，并且能够整除y0的数挑选出来，放到一个数组a中备用。
\item 搜索数组a中任意两个数字$P,Q$的排列，判断$P,Q$是否同时满足题干中的两个条件。
\end{compactitem}

本题需要的基础知识：
\begin{compactitem}
\item 知道用辗转相除法来求最大公约数gcd
\item 已知两个数P和Q，以及最大公约数gcd。如何求最小公倍数 $lcm = \frac {P\cdot Q} {gcd}$
\item 会估计空间和时间，挑选出来的数字用数组a存储，元素个数最多$10^6$，每个元素四字节，最多4MB。
实际上同时满足上述两个条件的数远远小于$10^6$，因此P和Q的排列也就远远小于$10^6$。
\end{compactitem}

\subsection{代码}
\begin{lstlisting}
#include <stdio.h>

#define N 1000010
 
int a[N]; 
int p; 
int x0, y0; 

int get_gcd(int a, int b)
{
	int c; 
	while(1) {
		c = a%b; 
		if (c==0) {
			return b;
		}
		a = b; 
		b = c; 
	}
	return 1; 
}

int get_lcm(int a, int b, int gcd)
{
	return a*b/gcd; 
}

int main()
{
	int i, j; 
	int r = 0; 
	scanf("%d %d", &x0, &y0); 
	
	for (i=x0; i<=y0; i+=x0) {
		if ((y0%i)==0) {
			a[p++] = i; 
		}
	}
	for (i=0; i<p; i++) {
		for (j=0; j<p; j++) {
			if (i==j)
				continue; 
			if (get_gcd(a[i], a[j])!=x0) 
				continue; 
			if (get_lcm(a[i], a[j], x0)!=y0) 
				continue; 
			r ++; 
		}
	}
	printf("%d\n", r); 
	return 0; 
} 
\end{lstlisting}


